Завдання Варіант № 26 Розрахувати параметри виконання алгоритму ШПФ з такими вхідними даними: Кількість точок 1024  Основа ШПФ 2  Прорідження часове  Частота роботи процесора 1,5 МГц  Розрядність вхідних даних 20 (10+10)  Тип вхідного інтерфейсу, пристрою Зовнішня пам’ять  Тип вихідного інтерфейсу, пристрою CAN   2. Аналіз (розробка) блок-схеми виконання заданої функції обробки сигналів та зображень на заданому типі процесора 2.1. Побудова графа алгоритму ШПФ з основою 2 Якщо число N є ступенем 2, то його можна записати як (N/2) * 2; аналогічно N/2 = (M/4) * 2 і т.д. В результаті елементи початкового одновимірного масиву можна розподілити таким чином, щоб елементарними операціями були двохточкові ШПФ. Для побудови графу N-точкового ШПФ з основою 2 потрібно визначити кількість ярусів (Nяр) графу та кількості метеликів (Nм) на кожному ярусі таким чином: Nяр = Log2N, для N=1024, Log21024 = 10; Nм = N/2 = 1024/2= 512. Граф-алгоритм для 32 точкового ШПФ за основою 2 показаний на рис. 2.
Рис.2. Граф 32-точкового ШПФ за основою 2 з прорідженням за часом На рис. 2 кільцям відповідають двохточкові ШПФ, стрілками зображено процедуру множення на повертаючі множники. Елементи пам’яті зображено точками та пронумеровано зверху вниз. Метелик ШПФ показаний на рис. 3, де
Рис. 3. Двохточкове ШПФ (Метелик) X, Y - результати базової операції; А, B - вхідні відліки; WN – повертаючих множники. 2.2. Біт інверсний порядок видачі даних Для реалізації ШПФ з прорідженням по частоті 1024-точкове ШПФ розділяють на 512 по 2-точкових ШПФ, далі на 256 4-точкових ШПФ, і так далі аж до 1024- точкового ШПФ. Ще однією особливістю алгоритму з прорідженням за частотою є те, що прямий порядок слідування даних на вході графу змінюється двійково-інверсним на виході. Тому для видачі даних в прямому порядку потрібно здійснити двійково-інверсну перестановку за правилом описаним в табл.1. Таблиця 1. Біт-інверсне прорідження Номер Двійкове представлення Двійкова інверсія Двійково-інверсний номер  0 0000000000 0000000000 0  1 0000000001 1000000000 512  2 0000000010 0100000000 256  3 0000000011 1100000000 768  4 0000000100 0010000000 128  5 0000000101 1010000000 640  6 0000000110 0110000000 384  7 0000000111 1110000000 896  8 0000001000 0001000000 64  9 0000001001 1001000000 576  10 0000001010 0101000000 320  11 0000001011 1101000000 832  … … … …  1021 1111111101 1011111111 383  1022 1111111110 0111111111 511  1023 1111111111 1111111111 1023   2.3. Блок-схема перетворення
Рис. 4. Блок-схема алгоритму 1024-точкового перетворення за основою 2 3. Розрахунковий розділ Частота роботи процесора:
, звідси цикл виконання команди:
. base – основа базової операції «метелик»; N – кількість точок вхідного перетворення; base=2 N=1024
– кількість етапів перетворення;
– кількість базових операцій «метелик» на одному етапі;
– кількість базових операцій у всьому перетворенні;


Для виконання базової операції «метелик» необхідно: 4 операцій множення; 6 операцій додавання; 10 операцій читання з пам`яті: - 2*2=4 (для читання дійсної та уявної частини вхідних відліків); - 3*2=6 (для читання дійсної та уявної частини комплексних коефіцієнтів); 4 операцій запису: - 2*2=4 (для запису дійсної та уявної частини вхідних відліків); В результаті на одну базову операцію припадає 24 операцій: Nна 1 мет=24 (оп). Тривалість виконання обчислення ШПФ:
Загальна частота роботи зовнішньої пам’яті(флешка):
, звідси цикл надходження команди:
. Тривалість надходження даних у процесор для обробки: Тнадх=2,5нс– такт надходження даних;
Частота роботи CAN шини:
, звідси цикл надходження команди:
. І оскільки шина CAN опрацьовує по 20 розрядів, необхідно ще помножити на 20. Тривалість виходу даних із процесора: Твих=63нс*20розрядів=1260 нс – такт виходу даних;
Тривалість надходження даних у процесор, тривалість обчислення ШПФ ...